#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    double myPow(double x, int n)
    {
        if (n == INT_MIN) {
            return 1.0 / (x * _myPow(x, -(n + 1)));
        }
        else if (n < 0) {
            return 1.0 / _myPow(x, -n);
        }

        return _myPow(x, n);
    }

private:
    double _myPow(double x, int n)
    {
        if (n == 0) {
            return 1.0;
        }
        else if (n == 1) {
            return x;
        }

        double half = _myPow(x, n / 2);

        if (n % 2 == 0) {
            return half * half;
        }
        else {
            return x * half * half;
        }
    }
};